package sort;

public class RadixSort {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        int[] arr = new int[800000];
        initArr(arr);
        radixSort(arr);
        //System.out.println(Arrays.toString(arr));
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
    }


    static void initArr(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }
    }
    public static void radixSort(int[] arr) {  //暂时处理不了负数,可以优化
        int max = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max)
                max = arr[i];
        }
        int maxLength = (max + "").length();

        int[][] bucket = new int[10][arr.length];
        int[] bucketElementCounts = new int[bucket.length];

        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                int digit = arr[j] / n % 10;
                bucket[digit][bucketElementCounts[digit]] = arr[j];
                bucketElementCounts[digit]++;
            }
            int index = 0;
            for (int k = 0; k < bucket.length; k++) {
                if (bucketElementCounts[k] != 0) {
                    for (int j = 0; j < bucketElementCounts[k]; j++) {
                        arr[index++] = bucket[k][j];
                    }
                }
                bucketElementCounts[k] = 0;
            }
        }
    }
}
